﻿using System;
using System.Runtime.InteropServices;
using System.Console;
using SCG = System.Collections.Generic;

using Nemerle.Assertions;
using Nemerle.Collections;
using Nemerle.Text;
using Nemerle.Utility;
using Nemerle.Utility.Getopt;

using GASS.OpenCL;
using Nemerle.OpenCL;

using Sample.Utils;

namespace Samples.GaussianNoise {

    class CliParameters {
        public ArrayLength  : int { get; set; }
        public FindMe       : int { get; set; }
        public SubDivisions : int { get; set; }
    }

    module Program {

        Main(args : array[string]) : void {
            def args = ParseCommandLine(args);
            def input = SetupArray(args);
            def output = ExecuteKernel(input, args);
            if(output[2] != 0)
                WriteLine($"Item $(args.FindMe) found at index $(output[0]).");
            else
                WriteLine($"There is no item $(args.FindMe) in array.");
            _ = ReadKey(true);
        }

        ParseCommandLine(args : array[string]) : CliParameters {
            def p = CliParameters();
            p.ArrayLength = 64;
            p.FindMe = 0;
            p.SubDivisions = 8;

            def cli_handlers = [
                CliOption.Int("-length", ["-l"],
                    "length of the input array",
                    x => p.ArrayLength = x),

                CliOption.Int("-find", ["-f"],
                    "element to be found",
                    x => p.FindMe = x),

                CliOption.Int("-divisions", ["-d"],
                    "number of subdivisions",
                    x => p.SubDivisions = x),
            ];

            Parse(Error, cli_handlers, NList.ToList(args));

            unless(MathUtils.IsPowerOf2(p.ArrayLength))
                p.ArrayLength = MathUtils.RoundToPowerOf2(p.ArrayLength) :> int;

            p
        }

        SetupArray(p : CliParameters) : array[int] {
            def rnd = Random(0);
            def max = p.ArrayLength * 20;

            def res = array(p.ArrayLength);
            res[0] = 0;
            for(mutable i = 1; i < res.Length; ++i)
                res[i] = res[i - 1] + rnd.Next(max);

            WriteLine(NList.ToList(res));

            res
        }

        ExecuteKernel(input : array[int], args : CliParameters) : array[int] {
            def output = array[0, 0, 0, 1];
            mutable global_lower_bound = 0;
            mutable global_upper_bound = input.Length - 1;
            mutable sub_div_size = (global_upper_bound - global_lower_bound + 1) / args.SubDivisions;

            using(context = Context(Device.DefaultAcceleratedDevice))
            using(input_buffer = context.CreateBufferWithData(input, CLMemFlags.ReadOnly))
            using(output_buffer = context.CreateBufferWithData(output, CLMemFlags.WriteOnly))
            using(program = context.BuildProgram(source, ProgramBuildOptions(context.Device)))
            {
                def kernel = program.GetKernel("binarySearch");
                kernel.Arguments[0] = output_buffer;
                kernel.Arguments[1] = input_buffer;
                kernel.Arguments[2] = args.FindMe;

                def global_threads = Kernel.NDRange(args.SubDivisions);
                def local_threads = Kernel.NDRange(1);

                while(sub_div_size > 0 && output[3] != 0) {
                    output[3] = 0;
                    context.Queue.WriteBuffer(output_buffer, 0, output_buffer.Size, output);

                    kernel.Arguments[3] = global_lower_bound;
                    kernel.Arguments[4] = global_upper_bound;
                    kernel.Arguments[5] = sub_div_size;

                    context.Queue.Execute(kernel, global_threads, local_threads);

                    context.Queue.ReadBuffer(output_buffer, 0, output_buffer.Size, output);
                    global_lower_bound = output[0];
                    global_upper_bound = output[1];
                    sub_div_size = (global_upper_bound - global_lower_bound + 1) / args.SubDivisions;
                }

                for(mutable i = global_lower_bound; i <= global_upper_bound; ++i)
                    when(input[i] == args.FindMe) {
                        output[0] = i;
                        output[1] = i + 1;
                        output[2] = 1;

                        Nemerle.Imperative.Return(output)
                    }
            }
            output[2] = 0;
            output
        }

        source =
<#

/**
 * One instance of this kernel call is a thread.
 * Each thread finds out the segment in which it should look for the element.
 * After that, it checks if the element is between the lower bound and upper bound
 * of its segment. If yes, then this segment becomes the total searchspace for the next pass.
 *
 * To achieve this, it writes the lower bound and upper bound to the output array.
 * In case the element at the left end (lower bound) matches the element we are looking for,
 * That is marked in the output and we no longer need to look any further.
 */

__kernel void
binarySearch(        __global uint4 * outputArray,
             __const __global uint  * sortedArray,
             const   unsigned int findMe,
             const   unsigned int globalLowerBound,
             const   unsigned int globalUpperBound,
             const   unsigned int subdivSize)
{
    unsigned int tid = get_global_id(0);

    /* lower bound and upper bound are computed from segment and total search space for this pass
     * The total search space is known from global lower and upper bounds for this pass.
     */
    unsigned int lowerBound = globalLowerBound + subdivSize * tid;
    unsigned int upperBound = lowerBound + subdivSize - 1;

    /* Then we find the elements at the two ends of the search space for this thread */
    unsigned int lowerBoundElement = sortedArray[lowerBound];
    unsigned int upperBoundElement = sortedArray[upperBound];

    /* If the element to be found does not lie between them, then nothing left to do in this thread */
    if( (lowerBoundElement > findMe) || (upperBoundElement < findMe))
    {
        return;
    }
    else
    {
        /* However, if the element does lie between the lower and upper bounds of this thread's searchspace
         * we need to narrow down the search further in this search space
         */

        /* The search space for this thread is marked in the output as being the total search space for the next pass */
        outputArray[0].x = lowerBound;
        outputArray[0].y = upperBound;
        outputArray[0].w = 1;

    }
}
#>;

    }

}